/***尚硅谷Java数据结构与java算法                 ***/
/***https://www.bilibili.com/video/BV1E4411H73v***/
/***二分查找         P78                       ***/
/***C++ 实现版本    written by Daniel           ***/

/* 查找的序列必须是有序数列，时间复杂度为O(log 2 N)*/
/*课后题，查找多个相同的数据*/
#include <iostream>
#include <list>

using std::cout;
using std::endl;
using std::list;

void binaryFind(int *arr, int size, int left, int right, int value,list<int>* resList)
{
    int mid = (left + right) / 2;
    cout << "mid=" << mid << endl;
    if (left > right)
    {
        return ;
    }

    if (arr[mid] > value)
    {
        return binaryFind(arr, size, left, mid - 1, value,resList);
    }
    else if (arr[mid] < value)
    {
        return binaryFind(arr, size, mid + 1, right, value,resList);
    }
    else
    {
        // list<int> resList;
        //找到了mid，需要向左和向右扩散；
        int i=mid,j=mid+1;
        //i向左扩散，j向右扩散
        while(arr[i]==arr[mid]&&i>=0){
            resList->push_back(i);
            i--;
        }
        while(arr[j]==arr[mid]&&j<size){
            resList->push_back(j);
            j++;
        }
        return;
    }
}

int main(int argc, char **argv)
{
    list<int>* resList=new list<int>;
    int array[14] = {1, 8, 10, 89,120, 563,768,768,768,893,999,1000, 1234,2000};
    int index = 0;
    binaryFind(array, 11, 0, 11, 100,resList);
    if (resList->empty()){
        cout<<"没有该元素"<<endl;
    }
    else {
        for(auto item:(*resList)){
            cout<<item<<"\t";
        }
        cout<<endl;
    }
}